{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Missing Number In Arithmetic Progression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: missingNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #等差数列中缺失的数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在某个数组&nbsp;<code>arr</code>&nbsp;中，值符合等差数列的数值规律：在&nbsp;<code>0 &lt;= i &lt; arr.length - 1</code>&nbsp;的前提下，<code>arr[i+1] - arr[i]</code>&nbsp;的值都相等。</p>\n",
    "\n",
    "<p>我们会从该数组中删除一个 <strong>既不是第一个 </strong>也<strong>&nbsp;不是最后一个的值</strong>，得到一个新的数组&nbsp;&nbsp;<code>arr</code>。</p>\n",
    "\n",
    "<p>给你这个缺值的数组&nbsp;<code>arr</code>，返回 <em>被删除的那个数</em> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [5,7,11,13]\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>原来的数组是 [5,7,<strong>9</strong>,11,13]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [15,13,12]\n",
    "<strong>输出：</strong>14\n",
    "<strong>解释：</strong>原来的数组是 [15,<strong>14</strong>,13,12]。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= arr.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= arr[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li>给定的数组 <strong>保证</strong> 是一个有效的数组。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [missing-number-in-arithmetic-progression](https://leetcode.cn/problems/missing-number-in-arithmetic-progression/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [missing-number-in-arithmetic-progression](https://leetcode.cn/problems/missing-number-in-arithmetic-progression/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,7,11,13]', '[15,13,12]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        diff = min(arr[1] - arr[0], arr[-1] - arr[-2])\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        l = 0\n",
    "        r = n-1\n",
    "        diff = (arr[r]-arr[l])/n\n",
    "        while l < r:\n",
    "            m = (l+r)//2\n",
    "            if arr[m] == arr[0] + m*diff:\n",
    "                l = m+1\n",
    "            else:\n",
    "                r = m\n",
    "        return int(arr[0] + diff*l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        return (arr[0] + arr[-1]) * (len(arr) + 1) // 2 - sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        diff = min(arr[1] - arr[0], arr[-1] - arr[-2])\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "        return arr[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        d = (arr[-1] - arr[0]) // n\n",
    "        return (n + 1) * arr[0] + n * (n + 1) * d // 2 - sum(arr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        diff = (arr[-1]-arr[0])//len(arr)\n",
    "        for i in range(0,len(arr)-1):\n",
    "            if arr[i+1]!=arr[i]+diff:\n",
    "                return arr[i]+diff\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr_len = len(arr)\n",
    "        diff = (arr[-1] - arr[0]) // arr_len\n",
    "\n",
    "        left = 0\n",
    "        right = arr_len - 1\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] == arr[0] + mid * diff:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        return arr[0] + diff * left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        sub = (arr[-1]-arr[0])/(len(arr))\n",
    "        for item in arr:\n",
    "            if item + sub in arr:\n",
    "                pass\n",
    "            else:\n",
    "                return int(item+sub)\n",
    "        \n",
    "                \n",
    "        return arr[0]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        return (arr[0] + arr[-1]) * (len(arr) + 1) // 2 - sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = len(arr) - 1\n",
    "        while r - l > 1:\n",
    "            mid = l + (r - l) // 2\n",
    "            if abs(arr[mid] - arr[l]) / (mid - l) > abs(arr[r] - arr[mid]) / (r - mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return (arr[l] + arr[r]) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        return (arr[0] + arr[-1]) * (len(arr)+1) // 2 - sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        # 题目说了不可能是第一个和最后一个位置\n",
    "        lo, hi = 0, len(arr) - 1\n",
    "        diff = (arr[-1] - arr[0]) // len(arr)\n",
    "        while lo < hi - 1:\n",
    "            mid = lo + (hi - lo + 1) // 2\n",
    "            if arr[mid] - arr[lo] == diff * (mid - lo):\n",
    "                lo = mid\n",
    "            else:\n",
    "                hi = mid\n",
    "        \n",
    "        return (arr[lo] + arr[hi]) // 2\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        target = (arr[-1]-arr[0])/len(arr)\n",
    "        lo = 0\n",
    "        hi = len(arr)-1\n",
    "        while(lo<hi):\n",
    "            mid = math.floor((hi+lo)/2)\n",
    "            if arr[mid] == arr[0] +mid*target:\n",
    "                lo = mid+1\n",
    "            else:\n",
    "                hi = mid\n",
    "        return int(arr[0]+target*lo)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        diff = (arr[-1] - arr[0]) // n \n",
    "\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] == arr[0] + mid * diff:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid \n",
    "        \n",
    "        return arr[0] + diff * left  \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        start, end = arr[0], arr[-1]\n",
    "        dif = int(abs(start - end) / len(arr))\n",
    "        if start == end:\n",
    "            return start\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "            if abs(arr[i] - arr[i + 1]) != dif:\n",
    "                if arr[i] > arr[i + 1]:\n",
    "                    return arr[i] - dif\n",
    "                else:\n",
    "                    return arr[i] + dif\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        return (len(arr) + 1) * (arr[0] + arr[-1]) // 2 - sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        # 题目说了不可能是第一个和最后一个位置\n",
    "        lo, hi = 0, len(arr) - 1\n",
    "        diff = (arr[-1] - arr[0]) // len(arr)\n",
    "        while lo < hi:\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            if arr[mid] == arr[0] + diff * mid:\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid\n",
    "        \n",
    "        return arr[0] + diff * lo\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        diff = (arr[len(arr)-1] - arr[0]) // len(arr)\n",
    "        if diff == 0:\n",
    "            return arr[0]\n",
    "\n",
    "        left, right = 0, len(arr)-1\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] - arr[0] == diff * mid:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return arr[0] + left * diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        # 这里使用二分查找可以快速确认缺失的值在哪边，主要是算法怎么写\n",
    "        arr_len = len(arr)\n",
    "        diff = (arr[-1] - arr[0]) // arr_len\n",
    "        # 二分查找\n",
    "        start, end = 0, arr_len - 1\n",
    "        while start < end:\n",
    "            m = (end + start) // 2\n",
    "            if arr[m] != arr[0] + m*diff:\n",
    "                end = m\n",
    "            else:\n",
    "                start = m\n",
    "            if end - start == 1:\n",
    "                return arr[0] + end*diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        d = (arr[-1] - arr[0]) // n\n",
    "        l, r = 0, n - 1\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if arr[mid] == arr[0] + d * mid:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return arr[l] + d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        diff = min(arr[1] - arr[0], arr[-1] - arr[-2])\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        \n",
    "        sum_true = (arr[0]+arr[-1])*(len(arr)+1)\n",
    "        sum_true/=2\n",
    "        result = sum_true - sum(arr)\n",
    "        return int(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        diff = min(arr[1] - arr[0], arr[-1] - arr[-2])\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "                elif arr[i + 1] - arr[i] == 0:\n",
    "                    return arr[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        return (arr[0] + arr[-1]) * (len(arr) + 1) // 2 - sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        interval_left_right = dict()\n",
    "        for i in range(len(arr)-1):\n",
    "            left, right = arr[i], arr[i+1]\n",
    "            interval_left_right[right-left] = (left, right)\n",
    "        k = max(interval_left_right.keys(), key=lambda x:abs(x)) \n",
    "        return interval_left_right[k][0]+k//2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        diff = min(arr[1] - arr[0], arr[-1] - arr[-2])\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "                elif arr[i + 1] - arr[i] == 0:\n",
    "                    return arr[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        sum1=(arr[0]+arr[-1])*(n+1)//2\n",
    "        sum2=sum(arr)\n",
    "        num=sum1-sum2\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        a = arr[1] - arr[0]\n",
    "        b = arr[-1] - arr[-2]\n",
    "\n",
    "        if a > 0:\n",
    "            diff = min(a, b)\n",
    "        else:\n",
    "            diff = max(a, b)\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "            if diff > 0:\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "            else:\n",
    "                if arr[i + 1] - arr[i] < diff:\n",
    "                    return arr[i] + diff\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        diff = min(arr[1] - arr[0], arr[-1] - arr[-2])\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "        return arr[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        start, end = arr[0], arr[-1]\n",
    "        dif = int(abs(start - end) / len(arr))\n",
    "        if start == end:\n",
    "            return start\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "            if abs(arr[i] - arr[i + 1]) != dif:\n",
    "                if arr[i] > arr[i + 1]:\n",
    "                    return arr[i] - dif\n",
    "                else:\n",
    "                    return arr[i] + dif\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        \n",
    "        for i in range(len(arr)-2):\n",
    "            diff1 = arr[i+1] - arr[i]\n",
    "            diff2 = arr[i+2] - arr[i+1]\n",
    "            if abs(diff2) > abs(diff1):\n",
    "                return arr[i+1] + diff1\n",
    "            elif abs(diff2) < abs(diff1):\n",
    "                return arr[i] + diff2 \n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        diff = min(arr[1] - arr[0], arr[-1] - arr[-2])\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "                elif arr[i + 1] - arr[i] == 0:\n",
    "                    return arr[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "        d = (arr[-1] - arr[0])//len(arr) #由于收尾肯定不是缺失的数，因此可以计算出公差d\n",
    "        l = 0\n",
    "        r = n-1\n",
    "        while l<=r:  #利用二分的思想\n",
    "            mid = (l+r)>>1\n",
    "            if mid+1<n: #限定范围\n",
    "                if arr[mid+1]-arr[mid] !=d:\n",
    "                    return arr[mid]+d\n",
    "            elif mid-1>0:#限定范围\n",
    "                if arr[mid]-arr[mid-1] !=d:\n",
    "                    return arr[mid-1]+d\n",
    "            \n",
    "            if arr[mid]-arr[l] == (mid-l)*d: #说明在[mid,r]中 \n",
    "                l = mid+1\n",
    "            else: # 那么一定在说明在[l,mid]中 \n",
    "                r = mid-1\n",
    "        return arr[r]+d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        total = (arr[0] + arr[-1])* (len(arr) + 1) //2\n",
    "        return total - sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        diff = min(arr[1] - arr[0], arr[-1] - arr[-2])\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        return self.answer_1(arr)\n",
    "\n",
    "    def answer_1(self, arr):\n",
    "        arr_len = len(arr)\n",
    "\n",
    "        diff = (arr[-1] - arr[0]) // arr_len\n",
    "\n",
    "        for index in range(arr_len - 1, 0, -1):\n",
    "            if arr[index] - arr[index - 1] != diff:\n",
    "                return arr[index] - diff\n",
    "        return arr[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        diff = (arr[-1] - arr[0]) // n\n",
    "\n",
    "        for i, num in enumerate(arr):\n",
    "            if num  != arr[0] + diff * i:\n",
    "                return arr[0] + diff * i\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right = 0, n\n",
    "        dis = (arr[-1]-arr[0]) / (n)\n",
    "        while left < right:\n",
    "            mid = (right-left) // 2 + left\n",
    "            if arr[mid] == arr[0] + (mid) * dis:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return int(arr[0] + left * dis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        diff = (arr[-1] - arr[0]) // len(arr)\n",
    "        l, r = 0, len(arr) - 1\n",
    "        while l<r:\n",
    "            mid = (l + r)//2\n",
    "            if arr[mid] == arr[0] + mid*diff:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        \n",
    "        return arr[0] + r*diff\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        d = (arr[-1] - arr[0]) // len(arr)\n",
    "        if d == 0:\n",
    "            return arr[0]\n",
    "        left, right = 0, len(arr)-1\n",
    "        mid = (left + right) // 2\n",
    "        while mid != left:\n",
    "            if arr[mid] - arr[left] == (mid - left) * d:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "            mid = (left + right) // 2\n",
    "        return arr[mid] + d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        a = arr[1] - arr[0]\n",
    "        for i in range(2, len(arr)):\n",
    "            b = arr[i] - arr[i-1]\n",
    "            if abs(a) < abs(b):\n",
    "                return arr[i-1] + a\n",
    "            elif abs(a) > abs(b):\n",
    "                return arr[0] + b\n",
    "            else:\n",
    "                pass\n",
    "        return arr[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        a = arr[1] - arr[0]\n",
    "        b = arr[-1] - arr[-2]\n",
    "\n",
    "        if a > 0:\n",
    "            diff = min(a, b)\n",
    "        else:\n",
    "            diff = max(a, b)\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "            if diff > 0:\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "            else:\n",
    "                if arr[i + 1] - arr[i] < diff:\n",
    "                    return arr[i] + diff\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        s = (arr[0]+arr[-1])*(len(arr)+1)//2\n",
    "        return s-sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        d = (arr[-1] - arr[0])//len(arr) #由于收尾肯定不是缺失的数，因此可以计算出公差d\n",
    "        l = 0\n",
    "        r = n-1\n",
    "        while l<=r:  #利用二分的思想\n",
    "            mid = (l+r)>>1\n",
    "            if mid+1<n: #限定范围\n",
    "                if arr[mid+1]-arr[mid] !=d:\n",
    "                    return arr[mid]+d\n",
    "            elif mid-1>0:#限定范围\n",
    "                if arr[mid]-arr[mid-1] !=d:\n",
    "                    return arr[mid-1]+d\n",
    "            \n",
    "            if arr[mid]-arr[l] == (mid-l)*d: #说明在[mid,r]中 \n",
    "                l = mid+1\n",
    "            else: # 那么一定在说明在[l,mid]中 \n",
    "                r = mid-1\n",
    "        return arr[r]+d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        return int((arr[0]+arr[-1])/2 *(len(arr)+1) - sum(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "\n",
    "        diff = min(abs(arr[1] - arr[0]), abs(arr[1] - arr[2]))\n",
    "        if arr[1] == arr[0]:\n",
    "            return arr[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i - 1] + diff != arr[i]:\n",
    "                return arr[i - 1] + diff\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        cnt = Counter()\n",
    "        for x, y in pairwise(arr):\n",
    "            cnt[x - y] += 1\n",
    "        \n",
    "        mx = 0\n",
    "        for k in cnt:\n",
    "            if cnt[k] > mx:\n",
    "                mx = cnt[k]\n",
    "                d = k\n",
    "            elif cnt[k] == mx:\n",
    "                if abs(k) < abs(d):\n",
    "                    d = k\n",
    "        for x, y in pairwise(arr):\n",
    "            if x - y == d: continue\n",
    "            return x - d \n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        diff = (arr[-1] - arr[0]) // n\n",
    "\n",
    "        l, r = 0, n - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if arr[mid] == arr[0] + mid * diff:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return arr[l] - diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        d = (arr[-1] - arr[0]) // n \n",
    "        l, r = 0, n - 1\n",
    "        while l + 1 < r:\n",
    "            mid = (l + r) // 2\n",
    "            if arr[mid] - arr[l] == d * (mid - l):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return (arr[l] + arr[r]) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        \n",
    "        delta = min([arr[1] - arr[0], arr[-1] - arr[-2]], key=lambda x: abs(x))\n",
    "        if delta == 0:\n",
    "            return arr[0]\n",
    "     \n",
    "        for i, a in enumerate(arr):\n",
    "            if delta + a != arr[i+1]:\n",
    "                return delta + a            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        diff = arr[1]-arr[0]\n",
    "        if diff==0:\n",
    "            return arr[0]\n",
    "        for i in range(1,n-1):\n",
    "            sub = arr[i+1]-arr[i]\n",
    "            if abs(diff)<abs(sub):\n",
    "                index = i+1\n",
    "                break\n",
    "            if abs(diff)>abs(sub):\n",
    "                index = i\n",
    "                break\n",
    "        return (arr[index]+arr[index-1])//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        # 二分查找\n",
    "        diff = (arr[-1] - arr[0]) // len(arr)\n",
    "        if diff == 0: return arr[0]\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] == arr[0] + mid * diff:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return arr[right] - diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        if len(set(arr)) == 1:\n",
    "            return arr[0]\n",
    "        n = len(arr)\n",
    "        diff = (arr[-1] - arr[0]) // n\n",
    "        start = arr[0]\n",
    "        while start < arr[-1]:\n",
    "            if start + diff not in arr:\n",
    "                return start + diff\n",
    "            start += diff"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
